package com.lmf.SingleLinkedList;

import java.util.Stack;

/**
 * 单向链表实例：
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //创建一个单链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //创建一些元素对象
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "吴用", "智多星");
        HeroNode hero3 = new HeroNode(3, "卢俊义", "玉麒麟");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(5, "王英", "矮脚虎");
        HeroNode hero6 = new HeroNode(5, "何家豪", "儿子");
        //添加进单链表
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);     //乱序添加元素
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);

        //显示单链表所有元素
        singleLinkedList.list();
        System.out.println("-----------------");

        //修改单链表元素
        singleLinkedList.update(hero6);
        singleLinkedList.list();
        System.out.println("-----------------");

        //删除单链表元素
        singleLinkedList.delete(5);
        singleLinkedList.delete(3);
        singleLinkedList.delete(4);
        singleLinkedList.list();
        System.out.println("-----------------");

        //统计单链表所有有效节点
        HeroNode head = singleLinkedList.getHead();
        Integer length = getLength(head);
        System.out.println("单链表有效节点个数："+length);
        System.out.println("-----------------");

        //获取倒数第n个节点
        int n = 1;
        HeroNode reciprocalNode = findReciprocalNode(head, n);
        System.out.println("倒数第"+n+"个节点："+reciprocalNode);
        System.out.println("-----------------");

        //实现单链表反转
        HeroNode heroNode = reverseNode(head);
        System.out.println("反转链表如下：");
        singleLinkedList.list();
        System.out.println("-----------------");

        //实现单链表的逆序打印：1.先反转，再打印  2.利用栈
        System.out.println("逆序打印链表如下：");
        reversePrint(head);
    }

    //求单链表的有效节点的个数
    public static Integer getLength(HeroNode head){
        //如果链表为空，返回0
        if (head.next == null) {
            return 0;
        }
        //创建统计有效节点个数的变量(不包括头节点)
        Integer sum = 0;
        //创建辅助头节点指针
        HeroNode temp = head.next;
        //遍历单链表，统计有效节点个数(不包括头节点)
        while (temp != null){
            //sum加一
            sum++;
            //后移指针
            temp = temp.next;
        }
        return sum;
    }

    // 求单链表的倒数第K个节点
    // 思路 1 编写一个方法接收head节点 接收index(倒数第index节点)
    //     2 先把链表变历 求出长度 length  去找到length-index的节点
    public static HeroNode findReciprocalNode(HeroNode head,int index){
        //如果链表为空，返回空
        if (head.next == null) {
            return null;
        }
        //遍历单链表，求出总长度
        Integer length = getLength(head);
        // 先做一个index的校验
        if(index <= 0 || index > length){
            return null;
        }
        //创建一个辅助头指针
        HeroNode temp = head;
        //然后遍历寻找 length-index 节点
        for (int i = 0; i <= length-index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //反转单链表(有点难度)：即1-9，变为9-1
    public static HeroNode reverseNode(HeroNode head){
        //若为空,若只有一个元素，则无需反转
        if (head.next == null || head.next.next == null) {
            return head;
        }
        //创建辅助头指针
        HeroNode temp = head.next;
        HeroNode next = null;
        //创建一个新头节点
        HeroNode reverseHeroNode = new HeroNode(0, null, null);
        //遍历被反转的单链表,每遍历一个，就将其取出，放到新链表的最前端
        while (temp != null){
            //先暂时保存当前节点的下一个节点，后面会用到
            next = temp.next;
            //temp的下一个节点，指向新链表的最前端
            temp.next = reverseHeroNode.next;
            //将原链表的元素取出放到新链表的最前端
            reverseHeroNode.next = temp;
            //后移指针
            temp = next;
        }
        //将head.next 指向 reverseHeroNode.next ，实现单链表反转
        head.next = reverseHeroNode.next;
        return head;
    }

    //利用栈，实现逆序打印单链表
    public static void reversePrint(HeroNode head){
        //若为空,返回空
        if (head.next == null) {
            return;
        }
        //创建一个栈
        Stack<HeroNode> stack = new Stack<>();
        //创建一个辅助指针
        HeroNode temp = head.next;
        //循环遍历单链表，入栈
        while (temp != null){
            stack.add(temp);
//            stack.push(head.next);
            temp = temp.next;
        }
        //遍历打印
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}

//定义一个单向链表 管理我们的英雄
class SingleLinkedList{
    // 初始化一下头结点  头结点不要动 不存放具体的数据
    private HeroNode head = new HeroNode(0,null,null);

    public HeroNode getHead() {
        return head;
    }

    // 添加方法:添加元素到单向链表
    	// 思路： 当不考虑编号顺序时
    	// 1. 找到当前链表的最后节点
    	// 2. 将最后的这个节点的next 指向 新节点
    public void add(HeroNode heroNode){
        // 因为 head节点不能动 我们需要一个辅助指针节点 temp
        HeroNode temp = head;
        // 遍历链表找到最后，让辅助指针temp从节点的data域，指向节点的next域
        while (true){
            if (temp.next == null) {//此时已到单链表最后，就直接返回，没必要再改变辅助指针的位置
                break;
            }
            //要保证头指针的next域不为空，后移辅助指针才有意义
            // 如果没有找到 每次添加元素，就将temp指针后移一位，此时辅助指针temp指向后一位元素
            temp = temp.next;
        }
        // 当退出white循环时, temp 就指向了链表的最后，并将数据添加到最后
        temp.next = heroNode;
    }

    // 第二种添加英雄的方式, 根据排名将英雄插入到指定位置
    // 如果有这个排名, 则添加失败 并给出提示
    public void addByOrder(HeroNode heroNode){
        // 因为头结点不能动 因此我们任然通过一个辅助指针(变量) 来帮助找到添加的位置
        // 因为是单列表 temp是要找到添加节点的前一个节点, 否则插入不了
        HeroNode temp = head;
        // 标志添加的编号是否存在 默认为false
        Boolean flag = false;
        //遍历单链表，寻找合适的元素插入位置
        while (true){
            //当到达链表的末尾时，结束循环，此时元素应该添加到链表末尾
            if (temp.next == null) {
                break;
            }
            if (temp.next.id == heroNode.id) {
                flag = true;    //说明编号重复，不能添加成功！
                break;
            }else if (temp.next.id > heroNode.id){
                //找到元素应该被添加的位置
                //当添加元素的id小于链表中已存在元素的id时，说明该添加元素就应该添加再该元素前面，
                // 即（temp与temp.next之间，因为temp在不断后移）
                break;
            }
            temp = temp.next;   //依次后移temp指针，寻找合适的插入位置，且防止出现死循环
        }
        //结束循环之后，根据flag值进行判断是否添加该元素
        if (flag) {
            //若为true，则不添加数据进链表
            System.out.println("说明编号重复，不能添加成功！");
        }else {
            //若为false，则将新数据添加进链表当前节点
            //将原节点的next域数据赋给新节点next域，相当于在单链表中增加一个元素，且保证后续链表不受影响
            heroNode.next = temp.next;
            //再将新节点next域数据赋给当前temp节点
            temp.next = heroNode;
        }
    }

    //修改节点信息，根据编号来修改，编号不能修改
    public void update(HeroNode heroNode){
        HeroNode temp = head;
        //判断链表是否为空
        if (temp.next == null) {
            System.out.println("链表为空，没有可以修改的信息！");
        }
        while (true){
            //若存在编号相同的元素，则进行信息更新，并结束循环;找到需要修改的位置
            if (temp.next.id == heroNode.id) {
                temp.next.name = heroNode.name;
                temp.next.nickName = heroNode.nickName;
                break;
            }
            if (temp.next == null){
                //若链表遍历完，不存在该编号的信息，则退出循环
                break;
            }
            //指针后移，依次循环
            temp = temp.next;
        }
    }

    // 删除节点
    //思路 1.head节点不能动 因此我们需要一个temp辅助节点找到删除节点的前一个节点
    //    2. 我们需要以temp节点的后一个节点的标号进行比较
    public void delete(int id){
        //判断链表是否为空
        HeroNode temp = head;
        Boolean flag = false;
        if (temp.next == null) {
            System.out.println("链表为空，没有数据可以删除！");
        }
        while (true) {
            if (temp.next == null){ // temp已经到链表的最后
                break;
            }
            if (temp.next.id == id){
                // 找到了待删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            // 可以删除
            HeroNode t = temp.next;
            temp.next = t.next;
        }else {
            System.out.println("没有找到该no=["+id+"]节点,无法删除");
        }

    }

    // 显示链表 遍历
    public void list(){
        // 判断链表为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 因为头结点不能动我们需要一个复制节点 temp
        HeroNode temp = head.next;
        while(true){
            // 输出这个节点的信息
            System.out.println(temp);
            //若到达单链表末尾，则结束循环
            if(temp.next == null){
                break;
            }
            // 若没有到达单链表末尾，则依次将temp 后移 不然是一个死循环
            temp = temp.next;
        }
    }


}

//定义一个英雄类，作为单链表的元素
class HeroNode{
    public int id;             //英雄编号
    public String name;        //英雄名字
    public String nickName;    //英雄外号
    public HeroNode next;      //指向下一个节点

    //创建构造方法
    public HeroNode(int id, String name, String nickName) {
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}